Binary Search Tree (BST)

A Binary Search Tree is a node-based binary tree data structure with this invariant:

  • Left subtree: keys less than the node's key.
  • Right subtree: keys greater than the node's key.
  • Both subtrees are themselves BSTs.

Formal Property

For any node \(v\), if \(u\) is in the left subtree of \(v\) and \(w\) is in the right subtree of \(v\):

$$\text{key}(u) < \text{key}(v) < \text{key}(w)$$

Try It Yourself